【V8 Blog 翻译】在V8中进行数组排序

Array.prototype.sort 是V8中最后一些用自托管JavaScript实现的内置函数之一。移植它给我们提供了一个尝试不同的算法和实现策略并最终在V8 v7.0/Chrome 70中使其稳定的机会。

背景

在JavaScript中排序是困难的。这篇博客文章将侧重于排序算法与JavaScript语言之间的一些怪异交互，并描述我们将V8迁移到一个稳定算法、使性能更可预测的旅程。

在比较不同的排序算法时，我们通过在记忆操作或者比较数量的渐进增长（即"大O"表示法）的限制来查看它们的最坏及平均性能。需要注意的是，在动态语言中，如JavaScript中，比较操作通常比内存访问贵一个数量级。这是由于在排序过程中比较两个值通常涉及到调用用户代码。

让我们看一个基于用户提供的比较函数将一些数字升序排列的简单示例。一个一致的比较函数在被提供的两个值分别是较小的、相等的或者较大的时候返回-1（或者任何其他负值）、0或者1（或者任何其他正值）。一个不遵循这种模式的比较函数是不一致的，并且可以有任意副作用，比如修改它被设计为排序的数组。

const array = [4, 2, 5, 3, 1];

function compare(a, b) {
  // 这里是任意的代码，例如`array.push(1);`。
  return a - b;
}

// A “typical” sort call.
array.sort(compare);

即使在下一个示例中，也可能发生对用户代码的调用。 "默认"比较函数会在两个值上调用toString，并在字符串表示上进行字典排序。

const array = [4, 2, 5, 3, 1];

array.push({
  toString() {
    // 这里是任意的代码，例如`array.push(1);`。
    return '42';
  }
});

// Sort without a comparison function.
array.sort();

访问器和原型链交互

这是我们离开规范并进入“实现定义”行为土地的部分。规范有一个条件列表，一旦满足，就允许引擎按照它认为合适的方式对对象/数组进行排序，或者完全不排序。引擎仍然必须遵循一些基本规则，但其他一切都基本上是不确定的。一方面，这给引擎开发者提供了尝试不同实现的自由。另一方面，尽管规范并不要求有任何合理的行为，但用户仍然期望有一些合理的行为。更复杂的是，“合理行为”并不总是明确的。

这一部分显示，还有一些Array＃sort的方面，其中引擎行为差异很大。这些是困难的边缘情况，正如上面提到的，要做什么才是“正确的事情”并不总是清楚的。我们强烈建议不要编写这样的代码；引擎不会为其优化。

第一个示例显示了一个数组，该数组有一些访问器（即 getters and setters）和不同JavaScript引擎中的“调用日志”。访问器是出现的第一个情况，其中结果排序顺序是由实现定义的：

const array = [0, 1, 2];

Object.defineProperty(array, '0', {
  get() { console.log('get 0'); return 0; },
  set(v) { console.log('set 0'); }
});

Object.defineProperty(array, '1', {
  get() { console.log('get 1'); return 1; },
  set(v) { console.log('set 1'); }
});

array.sort();

这是在各种引擎中该片段的输出。注意这里没有“正确”或“错误”的答案——规范将这个问题留给了各个引擎去实现！

// Chakra
get 0
get 1
set 0
set 1

// JavaScriptCore
get 0
get 1
get 0
get 0
get 1
get 1
set 0
set 1

// V8
get 0
get 0
get 1
get 1
get 1
get 0

#### SpiderMonkey
get 0
get 1
set 0
set 1

下一个例子展示了与原型链的交互。简洁起见，我们不显示调用日志。

const object = {
 1: 'd1',
 2: 'c1',
 3: 'b1',
 4: undefined,
 __proto__: {
   length: 10000,
   1: 'e2',
   10: 'a2',
   100: 'b2',
   1000: 'c2',
   2000: undefined,
   8000: 'd2',
   12000: 'XX',
   __proto__: {
     0: 'e3',
     1: 'd3',
     2: 'c3',
     3: 'b3',
     4: 'f3',
     5: 'a3',
     6: undefined,
   },
 },
};
Array.prototype.sort.call(object);

输出显示了排序后的对象。再次强调，这里没有正确的答案。这个例子只是展示了索引属性和原型链之间的交互有多奇怪：

// Chakra
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// JavaScriptCore
['a2', 'a2', 'a3', 'b1', 'b2', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined]

// V8
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// SpiderMonkey
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

在排序前后V8会进行的操作

注意：此部分在2019年6月更新以反映V8 v7.7中Array＃sort预处理和后处理的变化。

V8在实际排序任何东西之前有一个预处理步骤，以及一个后处理步骤。基本思想是将所有non-undefined值收集到临时列表中，对这个临时列表进行排序，然后将排序后的值写回实际的数组或对象中。这使得V8在排序过程中不用担心与访问器或原型链的交互。

规范期望Array ＃sort生成的排序顺序可以在概念上划分为三个部分：

所有non-undefined值按照比较函数排序。
所有的undefined值。
所有的空位，即不存在的属性。

实际的排序算法只需要应用于第一段。为了实现这一点，V8有一个预处理步骤大致如下：

让长度成为数组或对象的length属性的值。
让numberOfUndefineds为0。
对于范围 [0，length）中的每个值：
1. 如果值是空位：不做任何事情
2. 如果值为undefined：将numberOfUndefineds增加1。
3. 否则将值添加到临时列表元素中。

执行完这些步骤后，所有非undefined的值都包含在临时列表元素中。undefineds只是被简单地计数，而不是被添加到元素中。如上所述，规范要求把undefined排序到最后。然而，undefined的值实际上并没有传递给用户提供的比较函数，所以我们可以只计数出现了多少个undefined。

下一步实际上是对元素进行排序。有关TimSort的详细描述，请参见关于TimSort的部分。 https://v8.dev/blog/array-sort#timsort

排序完成后，排序后的值必须写回原始数组或对象。后处理步骤由处理概念段的三个阶段组成：

将所有的值从元素返回到范围为[0，elements.length)的原始对象中。
将所有从[elements.length，elements.length + numberOfUndefineds)的值设置为undefined。
删除范围从[elements.length + numberOfUndefineds，length)的所有值。

如果原始对象在排序范围内包含空位，那么步骤3是必要的。范围为[elements.length + numberOfUndefineds，length)的值已经被移动到前面，如果不执行步骤3，那么会产生重复的值。

历史

Array.prototype.sort和TypedArray.prototype.sort依赖于用JavaScript编写的相同的Quicksort实现。排序算法本身相当直接：基础是Quicksort，对于较短的数组（长度<10）使用插入排序作为后备。当Quicksort递归达到子数组长度为10时，也使用插入排序作为后备。插入排序对于较小的数组更有效。这是因为在分区后，Quicksort会被递归调用两次。每次这样的递归调用都会产生创建（和丢弃）一个栈帧的开销。

选择合适的枢纽(哨兵)元素在Quicksort中有很大的影响。V8采用了两种策略：

将枢纽元素选择为要排序的子数组的第一个、最后一个和第三个元素的中值。对于较小的数组，第三个元素就是中间元素。
对于较大的数组，取一个样本，然后排序，排序后的样本的中值作为上述计算中的第三个元素。

Quicksort的优点之一是它可以原地排序。内存开销来自于在对大数组排序时分配一个小数组供样本使用，以及log(n)的堆栈空间。缺点是它不是稳定的算法，而且有可能算法会遇到最糟糕的情况，即QuickSort退化为𝒪(n²)。

介绍V8 Torque

作为V8博客的热衷读者，您可能已经听说过CodeStubAssembler或简称CSA。CSA是一个V8组件，允许我们直接在C++中编写低级的TurboFan IR，然后使用TurboFan的后端将其转译成适当架构的机器代码。

CSA被大量用来编写JavaScript内置函数的所谓“快速路径”。一个内置函数的快速路径版本通常会检查某些不变性是否成立（例如在原型链上没有元素，没有访问器等），然后使用更快、更具体的操作来实现内置功能。这可能使执行时间比更通用的版本快一个数量级。

CSA的缺点是它真的可以被认为是一种汇编语言。使用显式标签和goto模拟控制流，这使得在CSA中实现更复杂的算法读起来困难且容易出错。

下面介绍 V8 Torque。Torque是一种领域特定语言，有类似TypeScript的语法，目前只使用CSA作为其唯一的编译目标。 Torque提供了与CSA几乎相同的控制级别，同时提供更高级别的构造，如while和for循环。此外，它是强类型，并将在将来包含安全检查，如自动越界检查，为V8工程师提供更强的保证。

首次在V8 Torque中重写的主要内置函数是TypedArray＃sort和Dataview操作。两者都进一步提供了反馈给Torque开发人员，以了解哪些语言特性需要使用，以及应该使用哪些习语来有效地编写内置函数。在撰写本文时，几个JSArray内置的自托管JavaScript后备实现已经移至Torque（例如Array＃unshift），而其他的则完全重写（例如Array＃splice和Array＃reverse）。

将Array＃sort移到Torque

初始的Array＃sort Torque版本或多或少是JavaScript直接实现的。唯一的区别是，对于较大的数组，而不是使用采样方法，计算枢纽(哨兵)元素的第三个元素是随机选择的。

这个方法工作得相当好，但是由于它仍然使用Quicksort，Array＃sort仍然不稳定。关于稳定的Array＃sort的请求是V8错误跟踪器中最古老的工单之一。实验将Timsort作为下一个排序算法，为我们提供了许多好处。首先，我们喜欢它是稳定的并提供一些不错的算法保证（参见下一节）。第二，Torque仍在进行中，使用Timsort实现更复杂的内置函数，如Array＃sort，产生了大量可以采取行动的反馈，影响了Torque。

Timsort

Timsort，由Tim Peters于2002年最初为Python开发，可以描述为一种自适应稳定的Mergesort变体。细节相当复杂，作者自己或维基百科页面描述是最好的，但基础易于理解。Mergesort通常以递归方式工作，而Timsort以迭代方式工作。它从左到右处理数组，并寻找所谓的runs。一个run只是已经排序的序列。包括以“错误的方式”排序的序列，因为这些序列可以简单地反向形成另一个run。在排序过程开始时，决定最小run长度，这取决于输入的长度。如果Timsort无法找到此最小run长度的自然runs，run将通过使用插入排序“人为地增强”。

以这种方式找到的run使用一个堆栈进行跟踪，该堆栈记住每个run的起始索引和长度。时不时地，堆栈上的run被融合在一起，直到只剩下一个排序的run。在决定合并哪些run时，Timsort试图保持平衡。一方面，您希望尽早尝试并合并，因为这些run的数据有很大的可能已经在缓存中，在另一方面，您希望尽可能晚地合并，以充分利用可能出现的数据模式。为了实现这一点，Timsort维护两个不变量。假设A、B和C是三个顶部的runs：

|C| > |B| + |A|
|B| > |A|

Pasted image 20240220161453.png

这张图片展示了|A| > |B|的情况，B被合并到两个运行中较小的一个。

请注意，Timsort只合并连续的run，这是为了保持稳定性，否则相等的元素会在run之间转移。另外，第一个不变量确保了运行长度的增长速度至少与斐波那契数列一样快，在我们知道最大数组长度时，可以给出运行堆栈大小的上限。

现在可以看出，已经排序的序列在𝒪(n)中排序，因为这样的数组会产生一个不需要合并的单一run。最坏的情况是𝒪(n log n)。这些算法属性以及Timsort的稳定性是我们最终选择Timsort而不是Quicksort的一些原因。

在 Torque 中实现 TimSort

通常，内置函数有不同的代码路径，这些路径在运行时根据各种变量进行选择。最通用的版本可以处理任何类型的对象，无论其是否为JSProxy，是否有拦截器或在获取或设置属性时是否需要进行原型链查找。在大多数情况下，通用路径相当慢，因为它需要考虑所有的可能性。但是，如果我们事先知道要排序的对象是一个只包含Smis的简单JSArray，那么所有这些昂贵的[[Get]]和[[Set]]操作可以被简单的Loads和Stores到FixedArray替换。主要的区别点是ElementsKind(其他博客中介绍)。

现在的问题变成了如何实现一个快速路径。核心算法对所有对象都是相同的，但我们访问元素的方式基于ElementsKind发生变化。我们可以通过在每个调用站点分派到正确的“访问器”来实现这一点。想象一下，对于每个“加载”/“存储”操作，我们根据选择的快速路径选择不同的分支。

另一种解决方案（这是首先尝试的方法）是为每个快速路径复制一次整个内置函数，并内联正确的加载/存储访问方法。这种方法对于Timsort来说是不可行的，因为它是一个大的内置函数，对每个快速路径进行复制最终需要总共106 KB，这对于单个内置函数来说实在太多了。

最后的解决方案略有不同。每个快速路径的每个加载/存储操作都被放入自己的“迷你内置函数”中。请参阅代码示例，该示例显示了FixedDoubleArrays的“加载”操作。

Load<FastDoubleElements>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  try {
    const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
    const value: float64 =
        LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
    return AllocateHeapNumberWithValue(value);
  }
  label Bailout {
    // The pre-processing step removed all holes by compacting all elements
    // at the start of the array. Finding a hole means the cmp function or
    // ToString changes the array.
    return Failure(sortState);
  }
}

作为比较，最通用的“加载”操作只是对GetProperty的调用。虽然上述版本生成了有效且快速的机器代码来加载并转换一个数字，但是，GetProperty是对另一个内置函数的调用，可能需要进行原型链查找或调用访问器函数。

builtin Load<ElementsAccessor : type>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  return GetProperty(context, elements, index);
}

然后，快速路径简单地成为一组函数指针。这就意味着我们只需要一份核心算法的副本，而一次性设置所有相关的函数指针。虽然这大大减少了需要的代码空间（降低到20k），但是每个访问站点都需要进行间接分支，代价是高昂的。最近使用内嵌内置函数的变更使这一问题更加严重。

排序状态

Pasted image 20240220162954.png

上图展示了“排序状态”。它是一个FixedArray，跟踪排序时所有需要的内容。每次调用Array＃sort时，都会分配这样一个排序状态。第4到7个条目是上述讨论的一组函数指针，构成了一个快速路径。

每次我们从用户JavaScript代码返回时，都使用“检查”内置函数，以检查我们是否可以在当前的快速路径上继续。它使用“初始接收者映射”和“初始接收者长度”来实现这一点。如果用户代码修改了当前对象，我们只需放弃排序运行，将所有指针重置为最通用的版本，然后重新开始排序过程。插槽8中的“退出状态”用于标识此重置。

“compare”条目可以指向两个不同的内置函数。一个调用用户提供的比较函数，而另一个实现默认比较，对两个参数调用toString，然后进行字典序比较。

其余的字段（除了快速路径ID）是特定于Timsort的。运行堆栈（如上所述）的初始大小为85，足以对长度为264的数组进行排序。临时数组用于合并运行。它的大小根据需要增长，但永不超过n/2，其中n是输入长度。

性能权衡

将排序从自托管的JavaScript移动到Torque会有性能权衡。由于Array＃sort是用Torque编写的，所以现在是一个静态编译的代码片段，这意味着我们仍然可以为某些ElementsKinds构建快速路径，但它永远不会像能够利用类型反馈的高度优化的TurboFan版本那么快。另一方面，在代码没有热到足以保证JIT编译的情况下，或者调用站点是megamorphic的情况下，我们就被限制在使用解释器或慢/通用版本。对自托管的JavaScript版本的解析、编译和可能的优化也是一个不必要的开销，而Torque实现则不需要这个开销。

虽然Torque的方法不会在排序性能上达到同样的峰值，但它确实避免了性能的下降。结果是，排序性能比以前更加可预测。请记住，Torque还在不断的变化中，除了针对CSA的目标，未来它可能还会针对TurboFan，允许对用Torque编写的代码进行JIT编译。

微基准测试

在我们开始使用Array＃sort之前，我们添加了很多不同的微基准测试，以便更好地理解重新实现将产生的影响。第一个图表展示了“正常”使用情况，即使用用户提供的比较函数对各种ElementsKinds进行排序。请记住，在这些情况下，JIT编译器可以做很多工作，因为排序几乎是我们全部的工作。这也允许优化编译器在JavaScript版本中内联比较函数，而在Torque情况下，我们有从内置到JavaScript的调用开销。然而，我们在几乎所有情况下都表现得更好。

Pasted image 20240220163401.png

下一个图表显示了Timsort处理完全排序的数组或已经按某种方式排序的子序列时的影响。该图表以Quicksort作为基准，展示了Timsort的加速（在“DownDown”情况下，加速高达17倍，此时的数组由两个反向排序的序列组成）。正如所见，除了在随机数据的情况下，Timsort在所有其他情况下都表现得更好，即使我们正在对PACKEDSMIELEMENTS排序，而在上面的微基准测试中，Quicksort的性能超过了Timsort。

Pasted image 20240220163408.png

Web工具基准测试

Web工具基准测试是一组工作负载的工具集合，通常由web开发人员使用，如Babel和TypeScript。该图表使用JavaScript QuickSort作为基准，并比较了Timsort相对于它的加速。在几乎所有的基准测试中，我们保留了相同的性能，chai是唯一的例外。

Pasted image 20240220163630.png

chai基准测试将其三分之一的时间花费在一个单独的比较函数（字符串距离计算）中。这个基准测试是chai本身的测试套件。由于数据的原因，Timsort在这种情况下需要进行更多的比较，这对整体运行时间的影响较大，因为花费在那个特定比较函数里的时间占了很大一部分。

内存影响

在浏览约50个网站（包括移动设备和桌面设备）时分析V8堆快照并未显示出任何内存回归或改进。这一方面令人惊讶：从Quicksort切换到Timsort引入了合并运行需要一个临时数组的必要性，而这个数组可能会比用于抽样的临时数组大得多。另一方面，这些临时数组的生命周期非常短（仅在调用排序函数的期间），并且在V8的新空间中可以非常快速地分配和丢弃。

总结

总的来说，我们对在Torque中实现的Timsort的算法性质和可预测的性能行为感觉更好。从V8 v7.0和Chrome 70开始，Timsort就可用了。快乐的排序吧！